package com.leetcode_mianshi_150;

class WordDictionary {

    private boolean isEnd;
    private WordDictionary[] next;


    public WordDictionary() {
        next = new WordDictionary[26];
    }
    
    public void addWord(String word) {
        WordDictionary node = this;

        for (int i = 0; i < word.length(); i++) {
            char op = word.charAt(i);

            if (node.next[op - 'a'] == null) {
                node.next[op - 'a'] = new WordDictionary();
            }

            node = node.next[op - 'a'];
        }

        node.isEnd = true;
    }
    
    public boolean search(String word) {
        WordDictionary node = this;
        return find(node, word, 0);

    }


    /**
     *
     * 递归匹配
     *
     * @param node
     * @param index
     * @param world
     * @return
     */
    public boolean find(WordDictionary node, String world, int index) {

        if (index >= world.length()) {
            return node.isEnd;
        }

        char op = world.charAt(index);
        boolean res = false;


        if (op == '.') {
            for (int i = 0; i < node.next.length; i++) {
                if (node.next[i] != null && find(node.next[i], world, index + 1)) {
                    return true;
                }
            }
        } else {
            if (node.next[op - 'a'] != null) {
                res = find(node.next[op - 'a'], world, ++index);
            }
        }

        return res;
    }
}

class  Main01 {
    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        //wordDictionary.addWord("dad");
        //wordDictionary.addWord("mad");
        //System.out.println(wordDictionary.search("pad")); // 返回 False
        System.out.println(wordDictionary.search("baddefa")); // 返回 True
        //System.out.println(wordDictionary.search(".ad")); // 返回 True
        //System.out.println(wordDictionary.search("b..")); // 返回 True
    }
}